package com.leetcode.problems045;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/jump-game-ii/
 * @Date 2021/12/09 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {

    class Tuple{
        public int index;
        public int step;

        public Tuple(int index,int step){
            this.index = index;
            this.step = step;
        }
    }

    /**
     *
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        int ans = 0;
        int end = 0;
        int maxPos = 0;
        for (int i = 0; i < nums.length - 1; i++)
        {
            maxPos = Math.max(nums[i] + i, maxPos);
            if (i == end)
            {
                end = maxPos;
                ans++;
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        int[] candidates = {2,3,1,1,4};
        System.out.println(new Solution().jump(candidates));
    }
}
